Metric dimension of directed graphs

Title: Metric dimension of directed graphs
Creator: Rajan, Bharati; Rajasingh, Indra; Cynthia, Jude Annie; Manuel, Paul
Relation: International Journal of Computer Mathematics Vol. 91, Issue 7, p. 1397-1406
Publisher Link: http://dx.doi.org/10.1080/00207160.2013.844335
Publisher: Taylor & Francis
Resource Type: journal article
Date: 2014
Description: A metric basis for a digraph G(V, A) is a set W⊂V such that for each pair of vertices u and v of V, there is a vertex w∈W such that the length of a shortest directed path from w to u is different from the length of a shortest directed path from w to v in G; that is d(w, u)≠d(w, v). A minimum metric basis is a metric basis of minimum cardinality. The cardinality of a minimum metric basis of G is called the metric dimension and is denoted by β (G). In this paper, we prove that the metric dimension problem is NP-complete for directed graphs by a reduction from 3-SAT. The technique adopted is due to Khuller et al. [Landmarks in graphs, Discrete Appl. Math. 70(3) (1996), pp. 217–229]. We also solve the metric dimension problem for De Bruijn and Kautz graphs in polynomial time.
Subject: metric basis; metric dimension; directed graph; NP-completeness; 3-SAT
Identifier: http://hdl.handle.net/1959.13/1301981
Identifier: uon:20385
Identifier: ISSN:0020-7160
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format